home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / unix / zip19p1.zoo / deflate.c < prev    next >
C/C++ Source or Header  |  1992-08-25  |  26KB  |  691 lines
  1. /*
  2.  
  3.  Copyright (C) 1990-1992 Mark Adler, Richard B. Wales, Jean-loup Gailly,
  4.  Kai Uwe Rommel and Igor Mandrichenko.
  5.  Permission is granted to any individual or institution to use, copy, or
  6.  redistribute this software so long as all of the original files are included
  7.  unmodified, that it is not sold for profit, and that this copyright notice
  8.  is retained.
  9.  
  10. */
  11.  
  12. /*
  13.  *  deflate.c by Jean-loup Gailly.
  14.  *
  15.  *  PURPOSE
  16.  *
  17.  *      Identify new text as repetitions of old text within a fixed-
  18.  *      length sliding window trailing behind the new text.
  19.  *
  20.  *  DISCUSSION
  21.  *
  22.  *      The "deflation" process depends on being able to identify portions
  23.  *      of the input text which are identical to earlier input (within a
  24.  *      sliding window trailing behind the input currently being processed).
  25.  *
  26.  *      The most straightforward technique turns out to be the fastest for
  27.  *      most input files: try all possible matches and select the longest.
  28.  *      The key feature is of this algorithm is that insertion and deletions
  29.  *      from the string dictionary are very simple and thus fast. Insertions
  30.  *      and deletions are performed at each input character, whereas string
  31.  *      matches are performed only when the previous match ends. So it is
  32.  *      preferable to spend more time in matches to allow very fast string
  33.  *      insertions and deletions. The matching algorithm for small strings
  34.  *      is inspired from that of Rabin & Karp. A brute force approach is
  35.  *      used to find longer strings when a small match has been found.
  36.  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
  37.  *      (by Leonid Broukhis).
  38.  *         A previous version of this file used a more sophisticated algorithm
  39.  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
  40.  *      time, but has a larger average cost and uses more memory. However
  41.  *      the F&G algorithm may be faster for some highly redundant files if
  42.  *      the parameter max_chain_length (described below) is too large.
  43.  *
  44.  *  ACKNOWLEDGEMENTS
  45.  *
  46.  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
  47.  *      I found it in 'freeze' written by Leonid Broukhis.
  48.  *      Thanks to many info-zippers for bug reports and testing.
  49.  *
  50.  *  REFERENCES
  51.  *
  52.  *      APPNOTE.TXT documentation file in PKZIP 2.0 distribution.
  53.  *
  54.  *      A description of the Rabin and Karp algorithm is given in the book
  55.  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
  56.  *
  57.  *      Fiala,E.R., and Greene,D.H.
  58.  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
  59.  *
  60.  *  INTERFACE
  61.  *
  62.  *      void lm_init (int pack_level, ush *flags)
  63.  *          Initialize the "longest match" routines for a new file
  64.  *
  65.  *      ulg deflate (void)
  66.  *          Processes a new input file and return its compressed length. Sets
  67.  *          the compressed length, crc, deflate flags and internal file
  68.  *          attributes.
  69.  */
  70.  
  71. #include "zip.h"
  72.  
  73. /* ===========================================================================
  74.  * Configuration parameters
  75.  */
  76.  
  77. /* Compile with MEDIUM_MEM to reduce the memory requirements or
  78.  * with SMALL_MEM to use as little memory as possible.
  79.  * Warning: defining these symbols affects MATCH_BUFSIZE and HASH_BITS
  80.  * (see below) and thus affects the compression ratio. The compressed output
  81.  * is still correct, and might even be smaller in some cases.
  82.  */
  83.  
  84. #ifdef SMALL_MEM
  85. #   define HASH_BITS  13  /* Number of bits used to hash strings */
  86. #else
  87. #ifdef MEDIUM_MEM
  88. #   define HASH_BITS  14
  89. #else
  90. #   define HASH_BITS  15
  91.    /* For portability to 16 bit machines, do not use values above 15. */
  92. #endif
  93. #endif
  94.  
  95. #define HASH_SIZE (unsigned)(1<<HASH_BITS)
  96. #define HASH_MASK (HASH_SIZE-1)
  97. #define WMASK     (WSIZE-1)
  98. /* HASH_SIZE and WSIZE must be powers of two */
  99.  
  100. #define NIL 0
  101. /* Tail of hash chains */
  102.  
  103. #define FAST 4
  104. #define SLOW 2
  105. /* speed options for the general purpose bit flag */
  106.  
  107. #ifndef TOO_FAR
  108. #  define TOO_FAR 4096
  109. #endif
  110. /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
  111.  
  112. /* ===========================================================================
  113.  * Local data used by the "longest match" routines.
  114.  */
  115.  
  116. typedef ush Pos;
  117. typedef unsigned IPos;
  118. /* A Pos is an index in the character window. We use short instead of int to
  119.  * save space in the various tables. IPos is used only for parameter passing.
  120.  */
  121.  
  122. #ifndef DYN_ALLOC
  123.   uch    far window[2L*WSIZE];
  124.   /* Sliding window. Input bytes are read into the second half of the window,
  125.    * and move to the first half later to keep a dictionary of at least WSIZE
  126.    * bytes. With this organization, matches are limited to a distance of
  127.    * WSIZE-MAX_MATCH bytes, but this ensures that IO is always
  128.    * performed with a length multiple of the block size. Also, it limits
  129.    * the window size to 64K, which is quite useful on MSDOS.
  130.    * To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would
  131.    * be less efficient since the data would have to be copied WSIZE/BSZ times)
  132.    */
  133.   Pos    far prev[WSIZE];
  134.   /* Link to older string with same hash index. To limit the size of this
  135.    * array to 64K, this link is maintained only for the last 32K strings.
  136.    * An index in this array is thus a window index modulo 32K.
  137.    */
  138.   Pos    far head[HASH_SIZE];
  139.   /* Heads of the hash chains or NIL */
  140. #else
  141.   uch    far * near window = NULL;
  142.   Pos    far * near prev   = NULL;
  143.   Pos    far * near head;
  144. #endif
  145.  
  146. long block_start;
  147. /* window position at the beginning of the current output block. Gets
  148.  * negative when the window is moved backwards.
  149.  */
  150.  
  151. local unsigned near ins_h;  /* hash index of string to be inserted */
  152.  
  153. #define H_SHIFT  ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH)
  154. /* Number of bits by which ins_h and del_h must be shifted at each
  155.  * input step. It must be such that after MIN_MATCH steps, the oldest
  156.  * byte no longer takes part in the hash key, that is:
  157.  *   H_SHIFT * MIN_MATCH >= HASH_BITS
  158.  */
  159.  
  160. unsigned int near prev_length;
  161. /* Length of the best match at previous step. Matches not greater than this
  162.  * are discarded. This is used in the lazy match evaluation.
  163.  */
  164.  
  165.       unsigned near strstart;      /* start of string to insert */
  166.       unsigned near match_start;   /* start of matching string */
  167. local int      near eofile;        /* flag set at end of input file */
  168. local unsigned near lookahead;     /* number of valid bytes ahead in window */
  169.  
  170. unsigned near max_chain_length;
  171. /* To speed up deflation, hash chains are never searched beyond this length.
  172.  * A higher limit improves compression ratio but degrades the speed.
  173.  */
  174.  
  175. local unsigned int max_lazy_match;
  176. /* Attempt to find a better match only when the current match is strictly
  177.  * smaller than this value.
  178.  */
  179.  
  180. int near good_match;
  181. /* Use a faster search when the previous match is longer than this */
  182.  
  183.  
  184. /* Values for max_lazy_match, good_match and max_chain_length, depending on
  185.  * the desired pack level (0..9). The values given below have been tuned to
  186.  * exclude worst case performance for pathological files. Better values may be
  187.  * found for specific files.
  188.  */
  189. typedef struct config {
  190.    int good_length;
  191.    int max_lazy;
  192.    unsigned max_chain;
  193.    uch flag;
  194. } config;
  195.  
  196. local config configuration_table[10] = {
  197. /*      good lazy chain flag */
  198. /* 0 */ {0,    0,    0,  0},     /* store only */
  199. /* 1 */ {4,    4,   16,  FAST},  /* maximum speed  */
  200. /* 2 */ {6,    8,   16,  0},
  201. /* 3 */ {8,   16,   32,  0},
  202. /* 4 */ {8,   32,   64,  0},
  203. /* 5 */ {8,   64,  128,  0},
  204. /* 6 */ {8,  128,  256,  0},
  205. /* 7 */ {8,  128,  512,  0},
  206. /* 8 */ {32, 258, 1024,  0},
  207. /* 9 */ {32, 258, 4096,  SLOW}}; /* maximum compression */
  208.  
  209. /* Note: the current code requires max_lazy >= MIN_MATCH and max_chain >= 4
  210.  * but these restrictions can easily be removed at a small cost.
  211.  */
  212.  
  213. #define EQUAL 0
  214. /* result of memcmp for equal strings */
  215.  
  216. /* ===========================================================================
  217.  *  Prototypes for local functions. Use asm version by default for
  218.  *  MSDOS but not Unix. However the asm version version is recommended
  219.  *  for 386 Unix.
  220.  */
  221. #ifdef ATARI_ST
  222. #  undef MSDOS /* avoid the processor specific parts */
  223. #endif
  224. #if defined(MSDOS) && !defined